/*
 *              main: Harness Class
 *
 *              Class Graph is called.
 *              Data from file is processed 
 *              Communities of significant structure returned.
 *              
 *              Reference Data: Zachary W. (1977).
 *              "An information flow model for conflict and fission in small groups." 
 *              Journal of Anthropological Research, 33, 452-473.
 *              
 *              Note:
 *	            zachary/data  file needs to be with binaries when executed
 *              Running Condidtions: Java SE, JVM.
 *
 *
 */
import java.io.FileNotFoundException;
import java.util.Scanner;

/**
 * Main class, the actual execution happens here.
 * See main method description for more
 */
public class main
{

    /**
     * Specifies a mode of execution of the algorithm,
     * current possibilities are Unconstrained - find the best community-structure for any # of communities
     * and ConstrainedByCommunityNumber - find a community structure with a certain # of communities
     */
    private enum Mode
    { 
        Unconstrained, //Find the partition of best modularity regardless of # of communities
        ConstrainedByCommunityNumber //Find the partition of best modularity, assuming a specific # of communities
    }
    
    /**
     * Encapsulates information about the mode of execution.
     * Contains the mode itself, and the number of communities to use as a constraint
     * if the ConstrainedByCommunityNumber mode is used
     */
    private static class ModeInfo
    {
        Mode mode;
        Integer num_communities = null; //Only used of the mode is ConstrainedByCommunityNumber, otherwiseis NULL
    }

    public static Boolean debug = false;

    /**
     * Gets the mode information from standard input
     * @param num_vertices the number of vertices in the graph, used to check the # of communities entered (if the ConstrainedByCommunityNumber mode is used) is valid.
     * @return a ModeInfo object containing the mode data as specified via standard input
     */
    private static ModeInfo getModeInfoFromUser(int num_vertices)
    {
        Scanner sc = new Scanner(System.in);
        
        String in_mode; 
        boolean in_mode_valid = false;
        
        Integer in_num_communities;
        boolean in_num_communities_valid = false;
        
        ModeInfo ret_mode_info = new ModeInfo();

        //Askfi the user if they want to constrain to a certain number of communities
        //If there vertices which are not connected to others then they will stay in their own community as the loop over edges will not merge them, this means the constraining will not work
        do
        {
            //disconnected components of the graph will never be connected. If the # of components > # of communities in constraint, the resulting communities will be the components of the graph as the algorithm will make its best-effort to merge communities
            System.out.print("Would you like to constrain the number of communities? (y/n) ");
            in_mode = sc.next();
            if (in_mode.compareTo("y") == 0)
            {
                ret_mode_info.mode = Mode.ConstrainedByCommunityNumber;
                in_mode_valid = true;

                System.out.println("Notice: Disconnected components of the graph will never be merged");
                do 
                {
                    System.out.println("How many communities to constrain to? ");
                    in_num_communities = sc.nextInt();

                    if (in_num_communities >= 1 && in_num_communities <= num_vertices)
                    {
                        in_num_communities_valid = true;
                        ret_mode_info.num_communities = in_num_communities;
                    }
                    else
                        System.out.print("Community number must be between 1 and the number of vertices");

                } while (!in_num_communities_valid);
            }
            else if (in_mode.compareTo("n")  == 0)
            {
                ret_mode_info.mode = Mode.Unconstrained;
                in_mode_valid = true;
            }
            else
                System.out.println("Answer must be 'y' or 'n'");
        } while (!in_mode_valid);
        
        return ret_mode_info;
    }
          
    /**
     * returns the edge such that joining the communities at its ends gives the greatest increase in modularity (or smallest decrease.)
     * If all edges are intra-community edges this method will return null (i.e in the case that there are no edges which connect different communities)
     * @param partition a partition of the graph
     * @return an edge object or NULL as specified
     */
    public static Edge getEdgeOfGreatestModularityIncrease(GraphPartition partition)
    {
        boolean edge_connects_different_communities;
        double current_increase;
        Double max_increase = null;
        Edge associated_edge = null;
        
        for (Edge e : partition.getEdgeArray())
        {
            edge_connects_different_communities = (e.firstEnd != e.secondEnd);

            if (edge_connects_different_communities)
            {
                current_increase = partition.getModularityIncrease(e);

                if (max_increase == null || (current_increase > max_increase))
                {
                    max_increase = current_increase;
                    associated_edge = e;
                }

            }
        }
        
        return associated_edge;
    }
          
    /**
     * gets the result community-structure according to the mode info, this is done via a greedy optimization scheme.
     * See more in the reference: Newman, Mark EJ. "Fast algorithm for detecting community structure in networks." Physical review E 69, no. 6 (2004): 066133.
     * This is where the actual logic of the algorithm happens.
     * @param graph a graph to partition
     * @param mode_info mode information which determines user-specified constraints on the algorithm
     * @return the result community-structure
     */
    public static CommunityCollection getResultCommunityCollection(Graph graph, ModeInfo mode_info)
    {
        boolean keep_merging = true;
        Edge associated_edge;
        GraphPartition partition = new GraphPartition(graph);
        double current_modularity = partition.getModularity();
        double max_modularity = current_modularity;
        
        //Stores the community collection of best modularity
        CommunityCollection community_collection_of_greatest_modularity = new CommunityCollection(partition.getCommunityCollection());
        CommunityCollection ret_community_collection = null;
      
        //Start merging communities
        while(keep_merging)
        {
            associated_edge = getEdgeOfGreatestModularityIncrease(partition);
        
            //Join the communities at the ends of associated_edge

            //associated edge may be null if there are no more edges left which connect different communities
            if (associated_edge != null)
            {
                //merge the communities and make sure the new modularity matches the value given by the getModularity function
                partition.mergeCommunities(associated_edge);
                current_modularity = partition.getModularity();

                //Adjust the maximum modularity
                if (mode_info.mode == Mode.Unconstrained 
                 && current_modularity > max_modularity)
                {
                        max_modularity = current_modularity;
                        community_collection_of_greatest_modularity = new CommunityCollection(partition.getCommunityCollection());
                }
                else if (mode_info.mode == Mode.ConstrainedByCommunityNumber
                      && mode_info.num_communities == partition.getNumCommunities())
                {
                        keep_merging = false;
                }
            }
            else
            {
                keep_merging = false;
            }
            
            if (mode_info.mode == Mode.Unconstrained)
                ret_community_collection = community_collection_of_greatest_modularity;
            else if (mode_info.mode == Mode.ConstrainedByCommunityNumber)
                ret_community_collection = partition.getCommunityCollection();
        }
        
        return ret_community_collection;
    }
    
    /**
     * Prints the result community collection to standard output
     * @param result_community_collection the result community collection
     * @param mode_info mode information specified by the user concerning the algorithm's execution
     */
    public static void printResultCommunityCollection(CommunityCollection result_community_collection, ModeInfo mode_info)
    {
        if (mode_info.mode == Mode.Unconstrained)
            System.out.println("Modularity of best partition: " + result_community_collection.getModularity());
        else if (mode_info.mode == Mode.ConstrainedByCommunityNumber)
            System.out.println("Modularity of best partition (constrained to " + mode_info.num_communities + " communities): " + result_community_collection.getModularity());
        
        result_community_collection.print();
    }
    
    /**
     * Outputs the result community collection to a GraphML file after asking the user if this is desired/
     * @param graph the graph which has been partitioned
     * @param result_community_collection the result community collection
     */
    public static void outputResultsToFileIfDesired(Graph graph, CommunityCollection result_community_collection)
    {
        Scanner sc = new Scanner(System.in);
        
        String in_ans; 
        boolean in_ans_valid = false;
        
        String in_filename;
        
        do
        {
            System.out.print("Would you like to output the results to a GraphML file? (y/n) ");
            in_ans = sc.next();
            if (in_ans.compareTo("y") == 0)
            {
                in_ans_valid = true;

                System.out.println("Specify a filename for the GraphML file (this will overwrite any existing file with this filename), by default the file is put in the 'output' folder, a '.graphml' extention will be added automatically: ");
                in_filename = sc.next();
                in_filename = "output/" + in_filename + ".graphml";
                
                if (result_community_collection.getNumCommunities() > GraphMLWriter.communityColors.length)
                    System.out.println("WARNING: Only " + GraphMLWriter.communityColors.length + " colors for communities have so far been specified in this application's code, communities from number " + GraphMLWriter.communityColors.length + " will all have the same color specified in the GraphML file");
                
                GraphMLWriter.partitionToGraphML(graph,result_community_collection,in_filename);
            }
            else if (in_ans.compareTo("n") == 0)
            {
                in_ans_valid = true;
            }
            else
                System.out.println("Answer must be 'y' or 'n'");
            
        } while (!in_ans_valid);

        
    }
    
    /**
     * The main method acquired the graph from a user-specified file.
     * It gets user specified mode information.
     * It then runs the actual algorithm, prints the results to standard output.
     * It also prints the results to a file if the user so desires.
     * @param args not used
     */
    public static void main(String[] args) throws FileNotFoundException
    {
        ModeInfo mode_info;
        CommunityCollection result_community_collection;
        
        //Reads the graph from a file
        //This creates the adjacency matrix, degree array and edge array for the graph
        Graph graph = new Graph();

        //Get the constraints desired by the user
        mode_info = getModeInfoFromUser(graph.getVertexCount());
     
        //Get the actual result of the algorithm under the constraints
        result_community_collection = getResultCommunityCollection(graph, mode_info);
        
        //Print algorithm results
        printResultCommunityCollection(result_community_collection, mode_info);
        
        //Output the results to a file if desired
        outputResultsToFileIfDesired(graph, result_community_collection);
        
    }
}



